package base.demo;

import base.sort.QuickSort;
import base.utils.PrintUtils;

public class QuickSortDemo {


    public static int[] array = {49, 38, 65, 97, 76, 13, 27, 31, 49, 78, 34, 12, 21, 64, 46, 1};
    public static int[] testArray = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    public static void main(String[] args) {
//        sort01();
        quickSortRecursive5(array, 0, array.length - 1);
        PrintUtils.print(array);
    }


    public static void sort01() {
        QuickSort sort = new QuickSort();
        int[] arr = sort.sort(array);
        PrintUtils.print(arr);
    }

    public static void sort02() {
        QuickSort sort = new QuickSort();
        sort.quickSort(array);
        PrintUtils.print(array);
    }

    public static void sortDemo01(int[] arr, int left, int right) {
        if (left < right) {
            int positionIndex = parition(arr, left, right);
            sortDemo01(arr, left, positionIndex - 1);
            sortDemo01(arr, positionIndex + 1, right);

        }
    }

    private static int parition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private static int parition2(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i < right; i++) {
            if (arr[pivot] > arr[i]) swap(arr, i, index++);
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }


    private static void swap(int[] array, int i, int j) {

//        System.out.print("i=" + i + ":" + array[i] + ";  j=" + j + ": " + array[j] + ";**");

        int sub = array[i];
        array[i] = array[j];
        array[j] = sub;

//        PrintUtils.print(array);
    }

    public static void quickSortRecursive2(int[] arr, int start, int end) {
        if (start >= end) return;
        int pivot = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] <= pivot && left < right) left++;
            while (pivot >= arr[right] && left < right) right--;
            if (arr[left] >= arr[end]) swap(arr, left, right);
        }
        if (arr[left] >= arr[end]) swap(arr, left, end);
        else left++;
        quickSortRecursive2(arr, start, left - 1);
        quickSortRecursive2(arr, left + 1, end);

    }


//    {49, 38, 65, 97, 76, 13, 27, 31, 49, 78, 34, 12, 21, 64, 46, 1};

    public static void quickSortRecursive3(int[] arr, int start, int end) {
        if (start >= end) return;
        int pivot = arr[end];

        int left = start, right = end - 1;

        while (left < right) {
            while (arr[left] < pivot && left < right) left++;

            while (pivot < arr[right] && left < right) right--;

//            if (left!=right)
            swap(arr, left, right);
        }

        if (arr[left] > arr[end]) swap(arr, left, end);
        else left++;

        System.out.println();
//        PrintUtils.print(arr);
        quickSortRecursive3(arr, start, left - 1);
        quickSortRecursive3(arr, left + 1, end);
    }

    public static void quickSortRecursive4(int[] arr, int start, int end) {
        if (start >= end) return;
        int pivot = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] < pivot && left < right) left++;
            while (pivot < arr[right] && left < right) right--;
            swap(arr, left, right);
        }
        if (arr[left] > arr[end]) swap(arr, left, end);
        else left++;
        quickSortRecursive4(arr, start, left - 1);
        quickSortRecursive4(arr, left + 1, end);
    }


    public static void quickSortRecursive5(int[] arr, int start, int end) {
        if(start>=end)return;
        int pivot =arr[end];
        int left=start;
        int right=end-1;

        while (left<right){
            while (arr[left]<pivot&&left<right)left++;
            while (pivot<arr[right]&&left<right)right--;
            swap(arr,left,right);
        }

        if (arr[left]>pivot)swap(arr,left,end);
        else left++;

        quickSortRecursive5(arr,start,left-1);
        quickSortRecursive5(arr,left+1,end);

    }


}












































